Dynamic Programming 2

Matrix-Chain Multiplication
2개의 행렬의 곱은 \Theta(n^3)이 소모된다.(스트라센 알고리즘을 이용시, \Theta(n^{lg7})이 소모)

2개 이상의 행렬을 연산 할 때, 행렬 연산 순서에 따라 연산의 횟수가 다르다.
행렬을 곱하는데 비용이 가장 적은 순서를 결정
괄호 묶는 방법 수를 세는 경우 P(n)=Σn−1k=1P(k)P(n−k) n≥2, P(1)=1 Ω(4n/n3/2)와 같다 m[i,j]를 i, j까지 행렬 곱을 수행할 때의 비용라고 정의할 때 m[i,j]=m[i,k]+m[k+1,j]+pi−1pkpj
#include <iostream>
#include <climits>
template <typename T>
struct twoPoint{
T *p1, *p2;
twoPoint(T* _p1, T* _p2): p1(_p1), p2(_p2) {}
~twoPoint(){
delete[] p1, p2;
}
};
struct Table{
int size;
int** table;
Table(int _size): size(_size){
this->table=new int*[this->size];
for(int i=0; i<this->size; ++i){
this->table[i]=new int[this->size];
}
}
~Table(){
for(int i=0; i<this->size; ++i) delete[] this->table[i];
delete[] this->table;
}
int* operator[](int n){
return this->table[n];
}
};
twoPoint<Table> MatrixChainOrder(int* p, int size){
int n=size-1;
Table* m=new Table(n);
Table* s=new Table(n-1);
for(int i=0; i<n; ++i) (*m)[i][i]=0;
for(int l=2; l<=n; ++l){ // chain length
for(int i=0; i<n-l+1; ++i){
int j=i+l-1;
(*m)[i][j]=INT_MAX;
for(int k=i; k<j; ++k){
int q=(*m)[i][k]+(*m)[k+1][j]+p[i]*p[k+1]*p[j+1];
if(q<(*m)[i][j]){
(*m)[i][j]=q;
(*s)[i][j-1]=k+1;
}
}
}
}
return twoPoint<Table>(m, s);
}
void PrintOptimalParens(Table* s, int i, int j){
if(i==j) std::cout<<"A"<<i;
else{
std::cout<<"(";
PrintOptimalParens(s, i, (*s)[i-1][j-2]);
PrintOptimalParens(s, (*s)[i-1][j-2]+1, j);
std::cout<<")";
}
}
int main(void){
int p[]={30, 35, 15, 5, 10, 20, 25};
int size=sizeof(p)/ sizeof(int);
twoPoint<Table> res=MatrixChainOrder(p, size);
PrintOptimalParens(res.p2, 1, 6);
return 0;
}
동적 프로그래밍을 위한 조건
1. 최적 부분 구조
2. 중복되는 부분 문제

동적 프로그래밍은 부분 문제의 개수 X 부분 문제에 대한 선택의 개수 만큼의 알고리즘 수행시간을 필요로 한다.
(각 부분 문제들이 독립적이지 않을 경우, 동적 프로그래밍을 사용할 수 없다.)